import java.util.Arrays;

/**
 * Creat with IntelliJ IDEA
 * Description
 * User: mamba24
 * Date: 2022-06-30
 * Time: 10:17
 * To BE A Better Person-2020-3-2
 */
public class TestSort {
    /**
     * 保持接口的统一性
     * @param arr
     * @param gap
     */
    public static void shell_sort(int[]arr,int gap){

        for(int i=gap;i<arr.length;i++){
            int j=i-gap;
            int tmp=arr[i];
            for(;j>=0;j-=gap){
                if(arr[j] > tmp) {
                    arr[j+gap] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+gap] = tmp;
        }
    }
    public static void shellsort(int[] arr){
        int gap=arr.length;
        while(gap>1){
            shell_sort(arr,gap);
            gap/=2;
        }
        shell_sort(arr,1);
    }

    public static void insertsort(int[] arr){
        int i=1;
        for(;i<arr.length;i++){
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0 ; j--) {
                if(arr[j] > tmp) {
                    arr[j+1] = arr[j];
                }else {
                    break;
                }
            }
            arr[j+1] = tmp;
        }
        }

    public static void selectsort(int[] arr){

        for (int i = 0; i < arr.length; i++) {
            int minindex=i;

            for (int j = i+1; j < arr.length; j++) {
                if(arr[j] < arr[minindex]) minindex=j;
            }

                int temp=arr[i];
                arr[i]=arr[minindex];
                arr[minindex]=temp;
        }

    }

    /**
     * 向下调整
     * @param root 要调整的数的根节点
     * @param len 数组的长度
     */
    public static void shiftDown(int[] arr,int root,int len){
        //找到子节点
        int child=root*2+1;
        while(child < len){
            //让child在左右子树较大的下面
            if((child+1)<len && arr[child]<arr[child+1]){
                child++;
            }
            if(arr[child]>arr[root]){
                //交换
                int temp=arr[child];
                arr[child]=arr[root];
                arr[root]=temp;
                root=child;
                child=root*2+1;
            }else{
                break;
            }

        }
    }
    public static void CreateHeap(int[] arr){
        for(int p=(arr.length-1-1)/2;p>=0;p--){
            shiftDown(arr,p,arr.length);
        }
    }
    public static void Heapsort(int[] arr){
        CreateHeap(arr);
        int end= arr.length-1;
        while(end>0){
            int temp=arr[0];
            arr[0]=arr[end];
            arr[end]=temp;
            shiftDown(arr,0,end);
            end--;
        }
    }

    public static void main(String[] args) {
        int[] arr={5,4,3,2,1};
        long st=System.currentTimeMillis();
        Heapsort(arr);
        long et=System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(" 堆排序:"+(et-st));
    }
    public static void main4(String[] args) {
        int[] arr={5,4,3,2,1};
        long st=System.currentTimeMillis();
        selectsort(arr);
        long et=System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(" 选择排序:"+(et-st));
    }
    public static void main3(String[] args) {
        int[] arr={5,4,3,2,1};
        long st=System.currentTimeMillis();
        shellsort(arr);
        long et=System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(" 希尔排序:"+(et-st));
    }
    public static void main2(String[] args){
        int[] arr={5,4,3,2,1};
        long st=System.currentTimeMillis();
        insertsort(arr);
        long et=System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println(" 插入排序:"+(et-st));
    }
    public static void main1(String[] args) {
        int[] arr={5,4,3,2,1};
        long st=System.currentTimeMillis();
        selectsort(arr);
        long et=System.currentTimeMillis();
        System.out.println(Arrays.toString(arr));
        System.out.println("选择排序:"+(et-st));

    }
}
